#include<conio.h>
#include<stdio.h>
#include<stdlib.h>
int a[100];
int n,x;
void inmenu(void)
{
	char ch;
	system("cls");
	printf("\n");
	printf("  0 - THOAT \n");
	printf("  1 - NHAP MANG \n");
	printf("  2 - TIM KIEM\n");
	printf("  3 - SAP XEP \n");
	do {
		ch=getch();
		switch(ch)
		{
			case 48: exit(0);
			break;
			case 49: menunhap();
			break;
			case 50: menutimkiem();
			break;
			case 51: menusapxep();
			break;
		}
	} while (ch<48||ch>51);
}
void menunhap(void)
{
	system("cls");
	printf("\n");
	printf("  0 - quay lai\n");
	printf("  1 - nhap ngau nhien \n");
	printf("  2 - nhap bang tay\n");
	printf("  3 - xem mang vua nhap\n");
	char ch;
	do {
		ch=getch();
		switch(ch)
		{
			case 48: inmenu();
			break;
			case 49: nhapngaunhien();
			break;
			case 50: nhapbangtay();
			break;
			case 51: xemmang();
			break;
		}
	} while (ch<48||ch>50);
}
void menutimkiem(void)
{
	system("cls");
	printf("\n");
	printf("  0 - quay lai\n");
	printf("  1 - tuan tu \n");
	printf("  2 - nhi phan\n");
	char ch;
	do {
		ch=getch();
		switch(ch)
		{
			case 48: inmenu();
			break;
			case 49: search_a(a,n,x);
			break;
			case 50: search_binary(a,n,x);
			break;
		}
	} while (ch<48||ch>50);
}

void menusapxep(void)
{
	system("cls");
	printf("\n");
	printf("  0 - quay lai\n");
	printf("  1 - noi bot \n");
	printf("  2 - doi cho truc tiep\n");
	printf("  3 - chon truc tiep\n");
	printf("  4 - chen tuan tu\n");
	char ch;
	do {
		ch=getch();
		switch(ch)
		{
			case 48: inmenu();
			break;
			case 49: noibot(a,n);
			break;
			case 50: tructiep(a,n);
			break;
			case 51: chonchuctiep(a,n);
            break;
            case 52: exit(0);
            break;
		}
	} while (ch<48||ch>52);
}
void noibot(int a[],int n)
{
    int i=0,j,t;
    system("cls");
    while(i<n-1)
    {
        for(j=n-1;j>i+1;j++)
        if(a[j]<a[j-1])
        {
            t=a[j];
            a[j]=a[j-1];
            a[j-1]=t
        }

    }
    xemmang();
}
void tructiep(itn a[],int n)
{
    int i=0,j,t;
    while(i<n-1)
    {
        for(j=i+1;j<n;j++)
            if(a[i]>a[j])
        {
            t=a[i];
            a[i]=a[j];
            a[j]=t
        }
        i++;
    }
    xemmang();
}
void chontructiep(int a[],int n)
{
    int i=0,j,t,min;
    while(i<n-1)
    {
        min=i;
        for(j=i+1;j<n;j++)
            if(a[min]>a[j]) min=j;
        if(min!=i)
        {
            t=a[min];
            a[min]=a[i];
            a[i]=t;
        }
    }
    xemmang();
}
void nhapngaunhien(void)
{
	int i;
	srand(time(NULL));
	system("cls");
	printf("   moi ban nhap so phan tu cua mang \n");
	scanf("%d",&n);
	for (i=0;i<n;i++)
	{
		a[i]=rand()%100;
	}
	//xuat mang ngau nhien
	/*
	printf("mang ngau nhien vua tao la \n");
	for (i=0;i<n;i++)
	{
		printf("%d ",a[i]);
	}
	getch();*/
	menunhap();
}
void nhapbangtay(void)
{
	int i;
	system("cls");
	printf("   moi ban nhap so phan tu cua mang \n");
	scanf("%d",&n);
	for (i=0;i<n;i++)
	{
		printf("a[%d]= ",i);
		scanf("%d",&a[i]);
	}
	//xuat mang ngau nhien
	/*printf("mang ban vua nhap la \n");
	for (i=0;i<n;i++)
	{
		printf("%d ",a[i]);
	}
	getch();*/
	menunhap();
}
void search_a(int a[],int n,int x)
{

    int i;
    system("cls");
    printf("nhap x");
    scanf("%d",&x);
    for(i=0;i<n;i++)
        if(a[i]==x) break;
    if(i<n) printf("%d",i);
    else printf("-1");
}
void search_binary(int a[],int n,int x)
{
    int l,r,m;
    l=0;
    r=n-1;
    printf("nhap x");
    scanf("%d",&x);
    while(l<=r)
    {
        m=(l+r)/2;
        if(a[m]==x)
            {
                printf("%d",m);
                return ;
            }

        if(a[m]<x) l=m+1;
        else r=m-1;

    }
    printf("-1");
    return ;
}
void xemmang(void)
{
	int i;
	system("cls");
	printf("mang ban vua nhap la \n");
	for (i=0;i<n;i++)
	{
		printf("%d ",a[i]);
	}
	getch();
	menunhap();
}
main()
{
	system("cls");
	inmenu();
}
